<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<!-- saved from url=(0052)https://www.lkozma.net/cuckoo_hashing_visualization/ -->
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:v="urn:schemas-microsoft-com:vml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"><style data-merge-styles="true"></style>
  
  <title>Cuckoo Hashing Visualization :: Laszlo Kozma</title>
  <link rel="stylesheet" type="text/css" href="style.css">

  </head>

  <body data-new-gr-c-s-check-loaded="14.998.0" data-gr-ext-installed="">
    <center><table width="80%">
    <tbody><tr><td>
    <h2>Cuckoo Hashing Visualization</h2>
    <p>Cuckoo hashing is an elegant method for resolving collisions in hash tables. It was invented in 2001 by Rasmus Pagh and Flemming Friche Rodler. It has the rare distinction of being easy to implement and efficient both in theory and practice.</p>
		<h3>Description</h3>
    <p>In the basic variant of Cuckoo hashing we use two hash tables <b>T<sub>1</sub></b> and <b>T<sub>2</sub></b> of equal size, and we index them with the hash functions <b>h<sub>1</sub></b>, respectively <b>h<sub>2</sub></b>. Here are the main operations:</p>
    <ul>
    <li><b>Search</b> couldn't be easier: an element <b>x</b> can exist in one of two locations: in <b>T<sub>1</sub></b> at position <b>h<sub>1</sub>(x)</b> or in <b>T<sub>2</sub></b> at position <b>h<sub>2</sub>(x)</b>. We can check both locations in constant time. </li><br>
    
    <li><b>Delete</b> is similarly easy: we look at the two possible locations, and if the element is there, we delete it.</li><br>
    
    <li><b>Insert</b> is a bit trickier: we put <b>x</b> in <b>T<sub>1</sub>[h<sub>1</sub>(x)]</b>. If there was some element <b>y</b> stored in that location, <b>y</b> must be evicted (thus the name "cuckoo" hashing). We put <b>y</b> in its other valid location <b>T<sub>2</sub>[h<sub>2</sub>(y)]</b>. If that location is occupied by some element <b>z</b>, we have to evict <b>z</b> and insert it in its other valid location <b>T<sub>1</sub>[h<sub>1</sub>(z)]</b>. We continue like this until we find an empty place and the process finishes, or until we give up because it starts to take too long (perhaps because we ran into a loop). If the latter happens, we conclude that insert failed, we stop and we rehash everything with new hash functions (increasing the table sizes if the tables are getting too full). It can be shown that insert takes constant time (on average), even if we account for the possible rehashing - assuming that the hash functions are sufficiently good.</li> 
    </ul>
    <p>For more details and variations on the theme read the <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.25.4189&amp;rep=rep1&amp;type=pdf">original article</a>, or the <a href="http://en.wikipedia.org/wiki/Cuckoo_hashing">wikipedia page</a> and references therein.</p>
    
    Here is a visualization of Cuckoo hashing. You can search, insert, or delete arbitrary elements via the text box in the middle.
    <br><br>
    <center>
		<table cellpadding="0" cellspacing="2">
			<tbody><tr>
				<td>
    			<canvas id="myCanvas1" width="300" height="500">
			    This text is displayed if your browser does not support HTML5 Canvas.
			    </canvas>
		    </td>
		    <td valign="top">
		    	<table><tbody><tr><td height="213"></td></tr></tbody></table>
			    <input id="inputx" type="text" maxlength="15" size="15" onkeyup="process()" spellcheck="false" data-ms-editor="true" style="background-color: white;"><br><br>
			    <center> <button id="insertbutton" type="button" style="font-size: 13px" onclick="insrt(1)">Insert</button> &nbsp; <button id="deletebutton" type="button" style="font-size: 13px" onclick="delt()">Delete</button> </center>
			    <br><br>
			    <center><div id="message"><font color="green">INSERT ok.</font></div></center>
		    <editor-squiggler><style>
  @media print {
    .ms-editor-squiggles-container {
      display:none !important;
    }
  }
  .ms-editor-squiggles-container {
    all: initial;
  }</style><div class="ms-editor-squiggles-container"></div></editor-squiggler></td>    
		    <td>
			    <canvas id="myCanvas2" width="300" height="500">
			    This text is displayed if your browser does not support HTML5 Canvas.
			    </canvas>
		    </td>
    	</tr>
    	<tr><td colspan="3">
    	<div align="right" style="font-size: 0.8em">© 2014 <a href="http://www.lkozma.net/" target="_new">László Kozma</a>
    	</div>
    	</td></tr>
    </tbody></table>
    </center>
    </td></tr>
    </tbody></table>
    </center>
  <script type="text/javascript" src="cuckoo.js"></script>
  

</body>